The invention relates generally to routers and switches and, more particularly, to routers and switches that support multiple classes of service for packet routing.
At network multiplexing points, such as switches or routers, the handling of frames or packets is generally determined by rules associated with classes of service to which given frames or packets are assigned. The classes of service essentially define acceptable packet or frame delays and probabilities of packet or frame loss. (As used herein, the term xe2x80x9cpacketxe2x80x9d refers to both frames and packets, and the term xe2x80x9crouterxe2x80x9d refers to both switches and routers.)
The packets are typically assigned to classes of service based on information contained in the packet and/or traffic management rules established by either a network supervisor or a service provider. All packets assigned to the same class receive the same treatment. Being assigned to a xe2x80x9chigherxe2x80x9d class ensures that a packet will have a shorter maximum transmission delay and a lower probability of loss. Being assigned to a xe2x80x9clowerxe2x80x9d class may mean a longer delay and/or a greater probability of loss.
Generally, the router maintains at each output port a buffer for holding packets in queues associated with the classes of service. The queues ensure that packets are delivered in order within the various classes of service, and that the associated rules for maximum delays and probabilities of loss can be enforced. Since each queue is essentially separately maintained, the more classes the router supports the more processing and storage capacity is required for a given number of output ports. To support xe2x80x9cxxe2x80x9d classes, for example, the router must set aside buffer storage locations for each of the x queues at each of its xe2x80x9cyxe2x80x9d ports. Further, it must determine for each queue whether or not a next packet should be retained or discarded. The router thus makes x*y separate calculations based on queue length and/or available associated storage locations to determine whether to retain or discard the packets, where xe2x80x9c*xe2x80x9d represents multiplication.
Network standards, such as the (revised) 802.1p standard, have relatively recently increased the number of classes of service to eight classes. Routers operating under prior standards support four classes of service, and thus, must be upgraded, for example, with increased storage capacities of the output port buffers, to support the increased number of classes. Such upgrading may be prohibitively expensive and/or it may not be feasible. Accordingly, what is needed is a mechanism to operate a router that supports a relatively small number of classes of service in an environment in which packets are assigned to a greater number of classes. Such a mechanism should, without requiring the enlarged storage and processing capabilities conventionally associated with supporting the greater number of classes, maintain service distinctions associated with the greater number of classes and more importantly retain the order of packets within each of the greater number of classes.
A router maps packets assigned to 2n+m classes of service into 2n classes of service and assigns the packets to 2m levels of loss-priority within each of the 2n classes. The router includes a classifier that uses n bits of an (n+m)-bit xe2x80x9cclass of service identifierxe2x80x9d to map the packets to the 2n classes, and the remaining m bits to assign the loss priorities. The router then controls packet retention/discard with a modified weighted random early detection scheme based in part on the 2n+m classes and in part on the 2n classes, to maintain the probability of loss distinctions and in-order packet handling associated with the 2n+m classes.
A scheduler controls the transmission of packets by each output port based on the 2n classes of service. The scheduler uses a weighted round robin scheme to ensure that packets from each of the classes are transmitted by each of the output ports within the prescribed maximum delay limits associated with the 2n+m classes of service.
The router includes an output buffer that holds the packets for all of the router""s output ports. The router maintains a xe2x80x9cfree queue,xe2x80x9d which links the buffer storage locations available for packet storage. To determine whether to retain or discard a given packet, the router compares a weighted average depth of the free queue with predetermined maximum and minimum thresholds that are associated with the particular one of the 2n+m classes of service to which the packet is assigned. If the weighted average exceeds the associated maximum threshold, the router retains the packet in a storage location that is then removed from the free queue and linked to a class of service per output port queue that corresponds to the class of service to which the packet is mapped by the classifier. If the weighted average depth falls below the associated minimum threshold, the router discards the packet. If the weighted average depth falls between the associated minimum and maximum thresholds, the router calculates a probability of discard and compares the probability to a xe2x80x9crandomxe2x80x9d value. The router discards the packet if the probability exceeds the random value, and otherwise retains the packet.
The maximum and minimum thresholds are set relative to one another such that the loss priorities associated with the 2n+m classes are maintained. As discussed below, the router makes only one weighted average queue depth calculation for the free queue, and uses this calculation to determine whether to retain or discard packets for the 2n classes of service. This is in contrast to prior known routers that must maintain at each output port separate average queue depths for each of the class of service per port queues.